package com.wk.exercise.leetcode;

/**
 * <pre>
 *      @author : wk <br/>
 *      e-mail : 122642603@qq.com <br/>
 *      time   : 2019/7/1 <br/>
 *      GitHub : https://github.com/wk1995 <br/>
 *      address: https://leetcode-cn.com/problems/height-checker/
 *      CSDN   : http://blog.csdn.net/qq_33882671 <br/>
 *      desc   : 高度检查器
 *
 * 学校在拍年度纪念照时，一般要求学生按照 非递减 的高度顺序排列。
 *
 * 请你返回至少有多少个学生没有站在正确位置数量。该人数指的是：能让所有学生以 非递减 高度排列的必要移动人数。
 *
 *  
 *
 * 示例：
 *
 * 输入：[1,1,4,2,1,3]
 * 输出：3
 * 解释：
 * 高度为 4、3 和最后一个 1 的学生，没有站在正确的位置。
 *  
 *
 * 提示：
 *
 * 1 <= heights.length <= 100
 * 1 <= heights[i] <= 100
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/height-checker
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * </pre>
 */
public class Q1051 implements Q {
    @Override
    public void answer() {
        int[] heights={1,1,4,2,1,3};
        System.out.println(heightChecker(heights));
    }

    private int heightChecker(int[] heights) {
        int[] arr = new int[101];
        for (int height : heights) {
            arr[height]++;
        }
        int count = 0;
        //height指学生高度，最低为1
        //index是heights序号
        for (int height = 1, index = 0; height < arr.length; height++) {
            while (arr[height]-- > 0) {
                if (heights[index++] != height) {
                    count++;
                }
            }
        }
        return count;
    }

}